﻿// 10211. 「一本通 6.4 例 3」Sumdiv.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;
/*
https://loj.ac/p/10211

题目描述
原题来自：Romania OI 2002

求 A^B 的所有约数之和 \bmod\ 9901。

输入格式
输入两个整数 A,B。

输出格式
输出答案 \bmod 9901。

2 3


15

2^3=8，8 的所有约数为 1,2,4,8，1+2+4+8=15,15\bmod 9901=15，因此输出 15。

数据范围与提示
对于全部数据，0<= A,B<= 5 X 10^7。
*/

const int MOD = 9901;
vector<pair<long long, long long >> vp;

int A, B;

void calc() {
	for (int i = 2; i * i <= A; i++) {
		long long t = 0;
		while (A % i == 0) {
			A /= i; t++;
		}
		if (t != 0) {
			vp.push_back({ i,t*B });
		}
	}
	if (A != 1) { vp.push_back({ A,B }); }
}


long long qmi(long long v, long long mi, long long MOD) {
	long long res = 1;
	while (mi) {
		if (mi & 1) {
			res *= v; res %= MOD;
		}
		mi >>= 1;
		v *= v; v %= MOD;
	}

	return res;
}


long long sum(long long v, long long mi) {
	if (mi == 0) return 1;
	long long res = 0;
	if (mi % 2 == 0) {
		res = qmi(v, mi, MOD) + ((1+qmi(v, mi / 2 ,MOD)) * sum(v,mi / 2-1)) % MOD;
	}
	else {
		//计算奇数幂的计算方式 或者转化成偶数幂(v,mi-1)加上 v^mi均可
		//res = qmi(v, mi, MOD) + sum(v, mi - 1) % MOD;  
		res = ((1 + qmi(v, mi / 2 + 1, MOD)) * sum(v, mi / 2)  ) %MOD;
	}

	return res % MOD;
}



int main()
{
	cin >> A >> B;
	calc();

	long long res = 1;
	for (int i = 0; i < vp.size(); i++) {
		long long v = vp[i].first; long long mi = vp[i].second;
		long long curr = sum(v, mi);
		res *= curr; res %= MOD;
	}

	cout << res << endl;

	return 0;
}
 